The present invention relates to information processing methods, decrypting methods, information processing apparatuses, and computer programs. More specifically, the present invention relates to an information processing method, a decrypting method, an information processing apparatus, and a computer program in which the subset difference (SD) method and the layered subset difference (LSD) method, which are currently known methods of broadcast encryption based on hierarchical tree structures, are improved using Rabin trees, so that the amount of secret information that each receiver has to hold securely, such as labels, is reduced, the amount of computation to be executed by each receiver is reduced, whereby efficient and secure information distribution is implemented.
Recently, various software data (hereinafter referred to as content), including audio data such as music, video data such as movies, game programs, and various application programs, is distributed via networks such as the Internet or via information recording media such as compact discs (CDs), digital versatile disks (DVDs), and mini disks (MDs). The content distributed is played back and used by various information processing apparatuses of users, such as personal computers (PCs), players, or game machines.
In many cases, the right to distributing content, such as music data or video data, is usually owned by the creator or seller of the content. Thus, when such content is distributed, certain usage restrictions are usually imposed so that only authorized users are allowed to use the content and unauthorized copying or the like is prevented.
Particularly, recording apparatuses or storage media for recording information digitally are becoming common recently. Such digital recording apparatuses and storage media allow repeated recording and playback without degrading content such as video or audio content. This has raised problems such as distribution of unauthorized copies of content over the Internet or unauthorized copying on recording media such as CD-Rs.
In a type of system that is intended to prevent such unauthorized use of content, content or a key for decrypting encrypted content is encrypted for distribution so that only specific authorized users or authorized devices can decrypt the data distributed. An example of such system is broadcast encryption based on a hierarchical tree structure.
Distribution of encrypted data, such as an encryption key, based on a hierarchical tree structure will be described with reference to drawings.
FIG. 1 shows a hierarchical tree structure that is a binary tree structure. The lowermost layer is referred to as leaves, and the root, branching points, and the leaves are referred to as nodes. The root is also referred to as the root node. In the binary hierarchical tree structure shown in FIG. 1, leaves are denoted by 8 to 15, nodes are denoted by 1 to 15, and the root is denoted by 1.
To the leaves 8 to 15 in the binary hierarchical tree structure, information processing apparatuses that use content, such as players or receivers, are assigned one by one.
Furthermore, node keys are assigned one by one to the respective nodes (including the leaves) of the tree. The node keys assigned to the leaves 8 to 15 are sometimes referred to as leaf keys.
To each information processing apparatus associated with a leaf, the node keys assigned to the nodes on the path from the leaf to the root are given. In the example shown in FIG. 1, eight information processing apparatuses are assigned respectively to the leaves 8 to 15, and node keys are assigned respectively to the nodes 1 to 15. For example, to an information processing apparatus 101 associated with the leaf 8, four node keys assigned to the nodes 1, 2, 4, and 8 are given. To an information processing apparatus 102 associated with the leaf 12, four node keys assigned to the nodes 1, 3, 6, and 12 are given. Each information processing apparatus securely holds these keys.
A method of sending information that can be obtained only by selected information processing apparatuses based on the above-described setting involving distribution of node keys will be described with reference to FIG. 2. As an example, a case will be considered where encrypted content generated by encrypting certain content such as music or video data is distributed by broadcasting or on recording media such as DVDs so that anybody can obtain the encrypted content, and a key for decrypting the encrypted content (content key Kc) is provided to specific users, i.e., users or information processing apparatuses authorized to use the content.
Let it be supposed that the information processing apparatus assigned to the leaf 14 is revoked as an unauthorized device, and other information processing apparatuses are authorized. In this case, ciphertexts are generated so that the information processing apparatus assigned to the leaf 14 cannot obtain the content key Kc while the other information processing apparatuses can obtain the content key Kc, and the ciphertexts are distributed via a network or as stored on recording media.
In this case, of the node keys other than the node key (represented by a cross sign in FIG. 2) of the information processing apparatus that is revoked, the content key is encrypted using some node keys shared by as many information processing apparatuses as possible, i.e., some node keys in an upper part of the tree.
In the example shown in FIG. 2, a set of ciphertexts generated by encrypting the content key Kc using the node keys of the nodes 2, 6, and 15 is provided. That is, ciphertexts E(NK2, Kc), E(NK6, Kc), and E(NK15, Kc) are generated and provided by network distribution or as stored on recording media. E(A, B) denotes data generated by encrypting data B using a key A. NKn denotes the node key of the n-th node. Thus, the ciphertext set includes three ciphertexts, i.e., data E(NK2, Kc) generated by encrypting the content key Kc using the node key NK2, data E(NK6, Kc) generated by encrypting the content key Kc using the node key NK6, and data E(NK15, Kc) generated by encrypting the content key Kc using the node key NK15.
By generating the three ciphertexts and sending the ciphertexts to all the information processing apparatuses, for example, via a broadcasting channel, each of the information processing apparatuses that are not revoked (the information processing apparatuses associated with the leaves 8 to 13 and the leave 15 in FIG. 2) can decrypt one of the ciphertexts using the one of the node keys it possesses and thereby obtain the content key Kc. On the other hand, the revoked information processing apparatus associated with the leave 14 possesses none of the three node keys NK2, NK6, and NK15 used for generating the three ciphertexts. Thus, even when the ciphertexts are received, the information processing apparatus cannot decrypt the ciphertexts and obtain the content key Kc.
An example of broadcast encryption method that has been reported in symposiums or the like is the method described in Advances in Cryptography-Crypto 2001, Lecture Notes in Computer Science 2139, Springer, 2001, pp. 41-62, D. Naor, M. Naor, and J. Lotspiech, “Revocation and Tracing Schemes for Stateless Receivers”. The broadcast encryption method described above is called the complete subtree (CS) method in the document.
However, when information is distributed using such a tree structure, messages that are to be broadcasted increase as the number of information processing apparatuses (user devices) associated with leaves increases. Furthermore, the amount of key information that has to be securely stored in each information processing apparatus (user device), such as node keys, also increases.
For example, in the CS method described above, when the total number of receivers (recipients) in the system is N and the number of revoked receivers, i.e., receivers that are not allowed to obtain broadcasted secret information, is r, the number of messages (ciphertexts) to be broadcasted is rlog(N/r), and the number of keys that each receiver has to hold in a secure memory is logN+1. In this specification, the base of logarithm is 2 except where otherwise stated.
In order to reduce manufacturing cost of receivers, it is desired to reduce the number of keys. Methods for reducing the number of keys have been proposed, for example, in January 2004, by Nojima et al, “Efficient Tree-based Key Management Using One-way Functions,” Proceedings of the Symposium on Cryptography and Information Security 2004, pp. 189-194, and Ogata et al, “Efficient Tree Based Key Management Based on RSA Function,” Proceedings of the Symposium on Cryptography and Information Security 2004, pp. 195-199.
According to the methods proposed in these documents, the number of keys that each receiver holds in the CS method is reduced to one based on the RSA cryptosystem. However, the use of the RSA cryptosystem leads to a large amount of computation, so that it is desired to reduce the amount of computation.
Methods that have been proposed to overcome these problems include the subset difference (SD) method and the layered subset difference (LSD) method, which is an improved version of the SD method. The SD method is described, for example, in Advances in Cryptography-Crypto 2001, Lecture Notes in Computer Science 2139, Springer, 2001, pp. 41-62, D. Naor, M. Naor, and J. Lotspiech, “Revocation and Tracing Schemes for Stateless Receivers”. The LSD method is described, for example, in Advances in Cryptography-Crypto 2002, Lecture Notes in Computer Science 2442, Springer, 2002, pp. 47-60, D. Halevy and A. Shamir, “The LSD Broadcast Encryption Scheme”.
In either method, when the total number of receivers (recipients) in the system is N and the number of revoked receivers, i.e., receivers that are not allowed to obtain broadcasted secret information, is r, the number of messages (ciphertexts) to be broadcasted is O(r). Advantageously, this value is smaller compared with the case of other methods such as the complete subtree method described earlier.
However, the number of keys (labels) that each receiver has to hold in a secure memory is O(log2N) in the SD method and O(log1+εN) in the LSD method, where ε is an arbitrary positive integer. The number of keys is larger compared with the case of other methods such as the complete subtree method, so that it is desired to reduce the number of keys.
As described above, when information is distributed using a tree structure, the number of messages, and the amount of key information that each information processing apparatus (user device) has to store securely, such as node keys, increases as the number of information processing apparatuses associated with leaves increases. Furthermore, the load of computation needed for calculating keys by receivers also raises problems. For example, when the amount of information that is to be stored in each user device increases and the computational load increases, the secure memory area and the processing capability of the user device have to be increased. This causes increase in manufacturing cost of user devices. Furthermore, processing delays occur due to the increased computational load.